/**
 * 
 */
package leetCode;

/**
 * 在m*n维乘法表找第k大的数 用二分：
 * 
 * @author zhongfang
 *
 */
public class KthlargestNumberinMultiplicationTable {
	public int findKthNumber(int m, int n, int k) {
		return binarySearch(m, n, 1, m * n, k);
	}

	/**
	 * 用二分搜索查找，left，right和mid指的是值（乘积）
	 * @param m
	 * @param n
	 * @param left
	 * @param right
	 * @param k
	 * @return
	 */
	private int binarySearch(int m, int n, int left, int right, int k) {
		while (left <= right) {
			int mid = (left + right) >> 1;
			if (getCount(mid, m, n) < k) {//乘积<=mid的个数
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return left;
	}

	/**
	 * 计算<=mid的乘法表中的个数
	 * @param mid
	 * @param m
	 * @param n
	 * @return
	 */
	private int getCount(int mid, int m, int n) {
		int count=0;
		for (int i = 1; i <= n; i++) {//行
			int y=mid/i;//这一列最多有多少满足乘积<=mid的
			count+=(m<=y)?m:y;
		}
		return count;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int m=2,n=3,k=6;
		System.out.println(new KthlargestNumberinMultiplicationTable().findKthNumber(m, n, k));
	}

}
